﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution39
{
    IList<IList<int>> res= new List<IList<int>>();
    public IList<IList<int>> CombinationSum(int[] candidates, int target)
    {
        IList<int> path = new List<int>();
        DFS2(candidates, target,path,0);
        return res;

    }

    private void DFS2(int[] candidates, int target, IList<int> path,int start)
    {

        if (target <= 0)
        {
            if (target == 0) {



                res.Add(new List<int>(path));

            }


            return;
        }


        for (int i = start; i < candidates.Length; i++) {//不能走回头路
    
            path.Add(candidates[i]);
            DFS2(candidates, target- candidates[i], path, i);//选择当前
            path.RemoveAt(path.Count-1);


         
           
        }
    }

    public IList<IList<int>> CombinationSum2(int[] candidates, int target)
    {
        IList<int> path = new List<int>();
        DFS(candidates, target, path, 0);
        return res;

    }

    private void DFS(int[] candidates, int target, IList<int> path, int start)
    {

        if(start>=candidates.Length)
        {
            return;
        }

        if (target <= 0)
        {
            if (target == 0)
            {
                res.Add(new List<int>(path));
            }


            return;
        }


        //不能走回头路


        Console.WriteLine(start);
        path.Add(candidates[start]);
            DFS(candidates, target - candidates[start], path, start);//选择当前
            path.RemoveAt(path.Count - 1);

        DFS(candidates, target, path, start + 1);//选择下一个，当前跳过,就不要target - candidates[start]

    }
}

class Program39
{


    static void Main39(string[] args)
    {
        Solution39 sol = new Solution39();
        int[] candidates = [2, 3, 6, 7];
        int target = 7;
        IList<IList<int>> res= sol.CombinationSum(candidates, target);
        for (int i = 0; i < res.Count; i++) { 
        
        
        for (int j = 0; j < res[i].Count; j++)
            {
                Console.Write(res[i][j]+",");
            }
            Console.WriteLine();
        }
    }
}
